package 动态规划.背包问题;

/**
 * @ClassName _494目标和
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2022/1/10 21:09
 * Version 1.0
 **/
public class _494目标和 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        int left = (target + sum)/2;
        if((target + sum) < 0 || (target + sum)%2 == 1){
            return 0;
        }
        int[] dp = new int[left + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = left; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
}
